package com.datastructure.dynamicprogramming;

/**
 * @author: 临晖
 * @date: 2023/11/12
 * @description:
 */


import jdk.nashorn.internal.runtime.regexp.JoniRegExp;

import java.awt.*;
import java.lang.annotation.Target;
import java.sql.Array;
import java.sql.Connection;
import java.util.*;
import java.util.List;

/**
 * 动态规划
 * <p>
 * 明白dp及其dp下标的含义
 * 确认递推公式
 * dp数组如何初始化
 * 确认遍历顺序
 * 举例推导dp数组
 */
public class Solution {


    /**
     * 509. 斐波那契数
     * 简单
     * 716
     * 相关企业
     * 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
     * <p>
     * F(0) = 0，F(1) = 1
     * F(n) = F(n - 1) + F(n - 2)，其中 n > 1
     * 给定 n ，请计算 F(n) 。
     *
     * @param n
     * @return
     */
    public int fib(int n) {
        ArrayList<Integer> list = new ArrayList<>();

        list.add(0);
        list.add(1);

        for (int i = 2; i <= n; i++) {
            list.add(list.get(i - 2) + list.get(i - 1));
        }

        return list.get(n);
    }


    /**
     * 70. 爬楼梯
     * 提示
     * 简单
     * 3.3K
     * 相关企业
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        //确认dp数组，以及下标i的含义
        //dp[i]表示爬到第i层楼有dp[i]种方式
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }
        int[] array = new int[n + 1];
        //确认递推公式
        //初始化数组
        array[0] = 1;
        array[1] = 2;
        //确认遍历顺序
        for (int i = 2; i < n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }

        return array[n - 1];
    }


    /**
     * 746. 使用最小花费爬楼梯
     * 提示
     * 简单
     * 1.4K
     * 相关企业
     * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        //dp数组，di[i]表示上第i个台阶所要花费的最少体力值
        int a = 0;
        int b = 0;
        int res = 0;
        for (int i = 2; i <= cost.length; i++) {
            res = Math.min(cost[i - 2] + a, cost[i - 1] + b);
            a = b;
            b = res;
        }

        return res;

    }


    /**
     * 62. 不同路径
     * 中等
     * 1.9K
     * 相关企业
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     * <p>
     * 问总共有多少条不同的路径？
     *
     * @param m
     * @param n
     * @return
     */
    int res = 0;

    public int uniquePaths(int m, int n) {
        //int[][] mg = new int[m][n];
        //unique(0, 0, mg);
        //return res;

        //确认dp数组及其下标的对应的含义
        int[][] mg = new int[m][n];
        //dp数组初始化
        for (int i = 0; i < m; i++) {
            mg[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {
            mg[0][i] = 1;
        }

        //dp遍历顺序
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //dp递推公式
                mg[i][j] = mg[i - 1][j] + mg[i][j - 1];
            }
        }

        return mg[m - 1][n - 1];

    }


    /**
     * 63. 不同路径 II
     * 提示
     * 中等
     * 1.2K
     * 相关企业
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     * 网格中的障碍物和空位置分别用 1 和 0 来表示
     *
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //单行，单列的情况：遇到1返回0，没遇到返回1


        //确认dp素组，并明白dp[i]的含义,dp[i]：到带该位置后，有dp[i]中方式
        //初始化dp数组
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {//如果在起点或终点出现了障碍，直接返回0
            return 0;
        }

        boolean flag = false;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                flag = true;
                obstacleGrid[i][0] = 0;
            }
            if (!flag) {        //如果是false，说明没遇到1，没遇到1之前，所有零都变成1
                obstacleGrid[i][0] = 1;
            }

        }

        flag = false;
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] == 1) {
                flag = true;
                obstacleGrid[0][j] = 0;
            }
            if (!flag) {
                obstacleGrid[0][j] = 1;
            }
        }

        //确认递推公式

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                    continue;
                }
                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            }
        }
        //确认遍历顺序
        //打印输出dp
        return obstacleGrid[m - 1][n - 1];
    }


    /**
     * 343. 整数拆分
     * 提示
     * 中等
     * 1.3K
     * 相关企业
     * 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
     * <p>
     * 返回 你可以获得的最大乘积 。
     * <p>
     * 示例 1:
     * <p>
     * 输入: n = 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1。
     * 示例 2:
     * <p>
     * 输入: n = 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     *
     * @param n
     * @return
     */
    public int integerBreak(int n) {
        //确认dp，明白dp[i]的含义：dp[i]表示数值i的乘积最大值
        int[] dp = new int[n + 1];
        //dp[i]初始化
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = dp[i] > j * (i - j) ? (dp[i] > j * dp[i - j] ? dp[i] : j * dp[i - j]) : (j * (i - j) > j * dp[i - j] ? j * (i - j) : j * dp[i - j]);
            }
        }

        return dp[n];
    }


    /***
     *
     * 96. 不同的二叉搜索树
     * 中等
     * 2.4K
     * 相关企业
     * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
     *
     *
     * 示例 1：
     *
     * 输入：n = 3
     * 输出：5
     * 示例 2：
     *
     * 输入：n = 1
     * 输出：1
     *
     * 提示：
     * 1 <= n <= 19
     *
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] treeNum = new int[n + 1];         //dp数组，dp[i]表示：有i个节点，有dp[i]种组成情况
        treeNum[0] = 1;
        for (int i = 1; i <= n; i++) {          //第一步：有n个节点，因此有n种头节点不同的情况,i = 1为头节点，i = 2为头节点，i = 3为头节点，...，就i = n为头节点
            for (int j = 1; j <= i; j++) {          //第二步：以i为头节点时，左右有j-1个节点，右别有i-j个节点的情况
                //而，左别有j-j个节点，又是以第一步，第二部计算得出的结果，这里直接借用前面的计算出来的结果
                treeNum[i] += treeNum[j - 1] * treeNum[i - j];
            }
        }

        return treeNum[n];
    }


    /**
     * 动态规划获得结果
     *
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {

        int goods = weight.length;      //获取物品数量
        //创建dp数组
        int[] dp = new int[bagSize + 1];
        //初始化dp数组


        //确认dp循环顺序
        for (int i = 0; i < goods; i++) {       //物品个数
            for (int j = bagSize; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }

        }

        System.out.println(dp[bagSize]);

        //// 创建dp数组
        //int goods = weight.length;  // 获取物品的数量
        //
        //
        ////dp[i][j]表示当前背包放的最大价值物品，i:表示0-i个物品，j:表示背包容量
        //int[][] dp = new int[goods][bagSize + 1];
        //
        ////初始化dp数组
        //
        //for (int i = 0; i <= bagSize; i++) {
        //    if (weight[0] <= i) {
        //        dp[0][i] = value[0];
        //    } else {
        //        dp[0][i] = 0;
        //    }
        //}
        //
        ////填充dp数组
        //for (int i = 1; i < goods; i++) {       //行，第i个物品
        //    for (int j = 1; j <= bagSize; j++) {                //列，背包容量j
        //        if (weight[i] > j) {        //物品容量大于背包容量，放不下，那么背包当前只有已经装入的物品，即当前的背包价值是：dp[i-1][j]
        //            dp[i][j] = dp[i - 1][j];
        //        } else {        //如果物品容量小于等于背包容量，那么，当前背包减去物品i的容量能放的最大价值加上物品i的价值 和 不放入物品i时的价值 相比那个大
        //            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        //        }
        //    }
        //}
        //
        //// 打印dp数组
        //for (int i = 0; i < goods; i++) {
        //    for (int j = 0; j <= bagSize; j++) {
        //        System.out.print(dp[i][j] + "\t");
        //    }
        //    System.out.println("\n");
        //}
    }
    //public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
    //
    //    // 创建dp数组
    //    int goods = weight.length;  // 获取物品的数量
    //
    //
    //    //dp[i][j]表示当前背包放的最大价值物品，i:表示0-i个物品，j:表示背包容量
    //    int[][] dp = new int[goods][bagSize + 1];
    //
    //    // 初始化dp数组
    //    // 创建数组后，其中默认的值就是0
    //    for (int j = weight[0]; j <= bagSize; j++) {
    //        dp[0][j] = value[0];
    //    }
    //
    //    // 填充dp数组
    //    for (int i = 1; i < weight.length; i++) {
    //        for (int j = 1; j <= bagSize; j++) {
    //            if (j < weight[i]) {
    //                /**
    //                 * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
    //                 * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
    //                 */
    //                dp[i][j] = dp[i-1][j];
    //            } else {
    //                /**
    //                 * 当前背包的容量可以放下物品i
    //                 * 那么此时分两种情况：
    //                 *    1、不放物品i
    //                 *    2、只放物品i，加上物品i，第一次过来的时候是只放物品i，第二次过来的时候是准备加上物品i（当前背包容量减去物品i的容量之后能放的最大的物品价值加上物品i的价值）
    //                 * 比较这两种情况下，哪种背包中物品的最大价值最大
    //                 */
    //                dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
    //            }
    //        }
    //    }
    //
    //    // 打印dp数组
    //    for (int i = 0; i < goods; i++) {
    //        for (int j = 0; j <= bagSize; j++) {
    //            System.out.print(dp[i][j] + "\t");
    //        }
    //        System.out.println("\n");
    //    }
    //}


    /**
     * 416. 分割等和子集
     * 中等
     * 1.9K
     * 相关企业
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }


        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) {
            return false;
        }

        int target = sum / 2;

        //创建dp数组
        int[] dp = new int[target + 1];
        //初始化dp数组

        //确认循环顺序
        for (int i = 0; i < nums.length; i++) {     //循环物品
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }

        if (dp[target] == target) {
            return true;
        }

        return false;
    }


    /**
     * 1049. 最后一块石头的重量 II
     * 提示
     * 中等
     * 783
     * 相关企业
     * 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
     * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
     * 如果 x == y，那么两块石头都会被完全粉碎；
     * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
     * 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
     * 示例 1：
     * 输入：stones = [2,7,4,1,8,1]
     * 输出：1
     * 解释：
     * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
     * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
     * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
     * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
     * 示例 2：
     * 输入：stones = [31,26,33,21,40]
     * 输出：5
     * 提示：
     * 1 <= stones.length <= 30
     * 1 <= stones[i] <= 100
     *
     * @param stones
     * @return
     */
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i = 0; i < stones.length; i++) {
            sum += stones[i];
        }


        int target = sum / 2;
        int[] dp = new int[target + 1];     //定义dp数组，dp[i]；表示”背包容量“为i能装的石头“价值“
        //初始化dp
        //确认循环顺序
        for (int i = 0; i < stones.length; i++) { //物品的个数
            for (int j = target; j >= stones[i]; j--) {
                //确认递推公式
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return sum - dp[target] - dp[target];
    }


    /**
     * 494. 目标和
     * 中等
     * 1.8K
     * 相关企业
     * 给你一个非负整数数组 nums 和一个整数 target 。
     * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
     * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
     * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
     * 示例 1：
     * 输入：nums = [1,1,1,1,1], target = 3
     * 输出：5
     * 解释：一共有 5 种方法让最终目标和为 3 。
     * -1 + 1 + 1 + 1 + 1 = 3
     * +1 - 1 + 1 + 1 + 1 = 3
     * +1 + 1 - 1 + 1 + 1 = 3
     * +1 + 1 + 1 - 1 + 1 = 3
     * +1 + 1 + 1 + 1 - 1 = 3
     * 示例 2：
     * 输入：nums = [1], target = 1
     * 输出：1
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 20
     * 0 <= nums[i] <= 1000
     * 0 <= sum(nums[i]) <= 1000
     * -1000 <= target <= 1000
     * <p>
     * <p>
     * 确定递推公式
     * 有哪些来源可以推出dp[j]呢？
     * <p>
     * 只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
     * <p>
     * 例如：dp[j]，j 为5，
     * <p>
     * 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
     * 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
     * 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
     * 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
     * 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包
     * 那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
     * 所以求组合类问题的公式，都是类似这种
     * dp[j] = dp[j - nums[i]]
     * <p>
     * 意思是：
     * 当得到dp[3]的时候，我已经知道了，凑齐背包容量为3的方式有dp[3]种，而这个时候，来个物品重量为2的物品，
     * 我们就可以得到，凑齐背包容量为5的方式有dp[5]种，即dp[5] = dp[5] + dp[3];  (dp[5]默认为0）
     * 即：来个容量为2的物品，凑齐容量为5的背包，有dp[3]种方式（dp[3]种方式可以凑齐容量为3的背包，那么dp[3]种方式每种加容量2，就是dp[3]种凑齐背包容量为5的方式）
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int numSum = 0;
        for (int i = 0; i < nums.length; i++) {
            numSum += nums[i];
        }
        //如果摸2有余数，说明不存在left         left = （sum + target) / 2;
        if ((numSum + target) % 2 == 1 || (numSum + target) < 0) {
            return 0;
        }
        //如果target 大于numsum，则也不存在
        if (target > numSum) {
            return 0;
        }

        //存在的话
        int left = (numSum + target) / 2;           //相当于背包容量
        int[] dp = new int[left + 1];

        //初始化dp
        dp[0] = 1;


        //确认循环顺序
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[left];

    }


    /**
     * 474. 一和零
     * 中等
     * 1.1K
     * 相关企业
     * 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
     * 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
     * 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
     * 输出：4
     * 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
     * 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
     * 示例 2：
     * <p>
     * 输入：strs = ["10", "0", "1"], m = 1, n = 1
     * 输出：2
     * 解释：最大的子集是 {"0", "1"} ，所以答案是 2
     *
     * @param strs
     * @param m
     * @param n
     * @return
     */
    public int findMaxForm(String[] strs, int m, int n) {
        //定义dp数组
        int[][] dp = new int[m + 1][n + 1];             //dp[i][j]表示：i个0，j个1的最大子集
        //初始化dp数组

        for (String str : strs) {
            int oneNum = 0;
            int zeroNum = 0;

            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }

            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }

        return dp[m][n];
    }


    /**
     * 518. 零钱兑换 II
     * 中等
     * 1.2K
     * 相关企业
     * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     * <p>
     * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
     * <p>
     * 假设每一种面额的硬币有无限个。
     * <p>
     * 题目数据保证结果符合 32 位带符号整数。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：amount = 5, coins = [1, 2, 5]
     * 输出：4
     * 解释：有四种方式可以凑成总金额：
     * 5=5
     * 5=2+2+1
     * 5=2+1+1+1
     * 5=1+1+1+1+1
     * 示例 2：
     * 输入：amount = 3, coins = [2]
     * 输出：0
     * 解释：只用面额 2 的硬币不能凑成总金额 3 。
     * 示例 3：
     * 输入：amount = 10, coins = [10]
     * 输出：1
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= coins.length <= 300
     * 1 <= coins[i] <= 5000
     * coins 中的所有值 互不相同
     * 0 <= amount <= 5000
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {
        //int sum = 0;                                  这里不适用，原因是：
        //for (int i = 0; i < coins.length; i++) {
        //    sum += coins[i];
        //}
        //
        //if (amount > sum) {
        //    return 1;
        //}

        //定义dp数组，dp[i]表示：金额为i的时候，有dp[i]中方式能凑齐dp[i]
        int[] dp = new int[amount + 1];
        //初始化dp数组
        dp[0] = 1;
        //确认循环顺序
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {      //因为每种物品有无数个，所以递增方式遍历，即，一种物品重复放入也可以
                dp[j] += dp[j - coins[i]];          //有几种装满方式，确认dp递推公式
            }
        }

        return dp[amount];

    }


    /**
     * 377. 组合总和 Ⅳ
     * 中等
     * 898
     * 相关企业
     * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
     * 题目数据保证答案符合 32 位整数范围。
     * <p>
     * 示例 1：
     * 输入：nums = [1,2,3], target = 4
     * 输出：7
     * 解释：
     * 所有可能的组合为：
     * (1, 1, 1, 1)
     * (1, 1, 2)
     * (1, 2, 1)
     * (1, 3)
     * (2, 1, 1)
     * (2, 2)
     * (3, 1)
     * 请注意，顺序不同的序列被视作不同的组合。
     * 示例 2：
     * 输入：nums = [9], target = 3
     * 输出：0
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 200
     * 1 <= nums[i] <= 1000
     * nums 中的所有元素 互不相同
     * 1 <= target <= 1000
     *
     * @param nums
     * @param target
     * @return
     */
    public int combinationSum4(int[] nums, int target) {
        //确认dp数组，dp[i]表示总和为i得背包，有dp[i]中方式组成
        int[] dp = new int[target + 1];
        //初始化dp
        dp[0] = 1;
        //确认循环顺序
        //
        //for (int j = nums[i]; j <= target; j++) {       //背包
        //    for (int i = 0; i < nums.length; i++) {     //物品
        //        dp[j] += dp[j - nums[i]];
        //    }
        //}

        for (int i = 1; i <= target; i++) {              //遍历背包
            for (int j = 0; j < nums.length; j++) {         //遍历物品
                if (nums[j] <= i) {
                    dp[i] += dp[i - nums[j]];
                }

            }
        }
        return dp[target];
    }


    /**
     * 卡码网
     * 57. 爬楼梯（第八期模拟笔试）
     * 时间限制：1.000S  空间限制：128MB
     * 题目描述
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * <p>
     * 每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * <p>
     * 注意：给定 n 是一个正整数。
     * <p>
     * 输入描述
     * 输入共一行，包含两个正整数，分别表示n, m
     * 输出描述
     * 输出一个整数，表示爬到楼顶的方法数。
     * 输入示例
     * 3 2
     * 输出示例
     * 3
     * 提示信息
     * 数据范围：
     * 1 <= m < n <= 32;
     * <p>
     * 当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。
     * <p>
     * 此时你有三种方法可以爬到楼顶。
     * <p>
     * 1 阶 + 1 阶 + 1 阶段
     * 1 阶 + 2 阶
     * 2 阶 + 1 阶
     *
     * @param n
     * @param m
     * @return
     */
    public int climbStairs(int n, int m) {          //n阶楼梯， 爬至多m阶楼梯
        //定义dp数组,dp[i]表示：第i阶楼梯有dp[i]种方式
        int[] dp = new int[n + 1];
        //初始化dp数组
        dp[0] = 1;
        //确认遍历顺序，先遍历“背包”，在遍历”物品“，因为这是个排列问题
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i - j >= 0) {           //i大于j，表示背包容量大于物品容量，可以装下
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[n];
    }


    /**
     * 322. 零钱兑换
     * 中等
     * 2.6K
     * 相关企业
     * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
     * <p>
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
     * 你可以认为每种硬币的数量是无限的。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：coins = [1, 2, 5], amount = 11
     * 输出：3
     * 解释：11 = 5 + 5 + 1
     * 示例 2：
     * <p>
     * 输入：coins = [2], amount = 3
     * 输出：-1
     * 示例 3：
     * <p>
     * 输入：coins = [1], amount = 0
     * 输出：0
     * <p>
     * 提示：
     * 1 <= coins.length <= 12
     * 1 <= coins[i] <= 231 - 1
     * 0 <= amount <= 104
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        //创建dp数组，dp[i]表示：数额为amount的时候，最少的硬币个数是dp[i]
        int[] dp = new int[amount + 1];
        //初始化dp数组
        for (int i = 0; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;

        }
        dp[0] = 0;


        for (int i = 0; i < coins.length; i++) {            //物品
            for (int j = coins[i]; j <= amount; j++) {      //背包
                //dp[j] += dp[j - coins[i]];      //计算组成数
                //在当给定容量下，装下价值最大的物品
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {

                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }

        if (dp[amount] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[amount];

    }


    /**
     * 279. 完全平方数
     * 中等
     * 1.9K
     * 相关企业
     * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
     * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
     * <p>
     * 示例 1：
     * 输入：n = 12
     * 输出：3
     * 解释：12 = 4 + 4 + 4
     * 示例 2：
     * 输入：n = 13
     * 输出：2
     * 解释：13 = 4 + 9
     * 提示：
     * 1 <= n <= 104
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        //定义dp数组,dp[i]表示：组成数值为i的数字的完全平方数的最小数量为dp[i]
        int[] dp = new int[n + 1];
        //初始化dp
        for (int i = 0; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        dp[0] = 0;
        //确认递推公式    dp[j] = Math.min(dp[j], dp[j - res] + 1)， res = i * i;
        //确认循环顺序
        for (int i = 1; i <= Math.sqrt(n) + 1; i++) {        //物品
            int res = i * i;
            for (int j = res; j <= n; j++) {
                if (dp[j - res] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - res] + 1);
                }
            }
        }

        return dp[n];

    }


    /**
     * 139. 单词拆分
     * 中等
     * 2.3K
     * 相关企业
     * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     * <p>
     * 示例 1：
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
     * 示例 2：
     * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * 输出: true
     * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     * 注意，你可以重复使用字典中的单词。
     * 示例 3：
     * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * 输出: false
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        //定义dp数组，dp[i]表示单词长度为i的字符串可以被拼接出来dp[i] = true;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        //for (int i = 0; i < wordDict.size(); i++) {
        //    S
        //    for (int j = word.length(); j <= s.length(); j++) {
        //        if (isEquals(s.substring(j - word.length(), j), word) && dp[j - word.length()]) {
        //            dp[j] = true;
        //        }
        //    }
        //}

        for (int i = 0; i <= s.length(); i++) {         //背包
            for (int j = 0; j < wordDict.size(); j++) {     //物品
                String word = wordDict.get(j);
                if (i - word.length() >= 0) {
                    if (isEquals(s.substring(i - word.length(), i), word) && dp[i - word.length()]) {
                        dp[i] = true;
                    }
                }
            }
        }

        return dp[s.length()];
    }


    public boolean isEquals(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return false;
        }

        if (s1 == s2) {
            return false;
        }

        return s1.equals(s2);
    }


    /**
     * 198. 打家劫舍
     * 中等
     * 2.8K
     * 相关企业
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     * <p>
     * <p>
     * 示例 1：
     * 输入：[1,2,3,1]
     * 输出：4
     * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     * 偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 2：
     * 输入：[2,7,9,3,1]
     * 输出：12
     * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
     * <p>
     * 提示：
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 400
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        //定义dp数组，dp[i]表示，dp[i]表示：第i间房包括前i间房屋最多偷了dp[i]元
        if (nums != null && nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        //初始化dp
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[nums.length - 1];
    }


    /**
     * 213. 打家劫舍 II
     * 提示
     * 中等
     * 1.5K
     * 相关企业
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     * <p>
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [2,3,2]
     * 输出：3
     * 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
     * 示例 2：
     * 输入：nums = [1,2,3,1]
     * 输出：4
     * 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     * 偷窃到的最高金额 = 1 + 3 = 4 。
     * 示例 3：
     * 输入：nums = [1,2,3]
     * 输出：3
     * <p>
     * 提示： 环装数组，三种情况 1.去头   2.去尾    3.掐头去尾（2，3包括1）
     * <p>
     * 1 <= nums.length <= 100
     * 0 <= nums[i] <= 1000
     *
     * @param nums
     * @return
     */
    public int rob1(int[] nums) {
        if (nums != null && nums.length == 1) {
            return nums[0];
        }

        //第一种情况

        int res1 = getRobMax(nums, 1, nums.length - 1);
        //第二种情况
        int res2 = getRobMax(nums, 0, nums.length - 2);

        return Math.max(res1, res2);
    }

    public int getRobMax(int[] nums, int start, int end) {
        if (end - start + 1 == 1) {
            return nums[start];
        }
        //定义dp数组,dp[i]表示前i个包括i最大的钱数
        int[] dp = new int[nums.length];
        //初始化
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);

        //确认循环顺序
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[end];
    }


    /**
     * 337. 打家劫舍 III
     * 中等
     * 1.9K
     * 相关企业
     * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
     * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
     * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
     *
     * @param root
     * @return
     */
    public int rob2(TreeNode root) {
        if (root != null && root.left == null && root.right == null) {
            return root.val;
        }

        int[] arr = rotTree(root);
        return Math.max(arr[0], arr[1]);

    }

    //后续遍历[不偷，偷]
    public int[] rotTree(TreeNode curr) {
        if (curr == null) {
            return new int[]{0, 0};
        }

        //左右中
        int[] left = rotTree(curr.left);
        int[] right = rotTree(curr.right);

        //中
        //如果当前不偷，那么左右可偷可不偷，主要是看哪个大
        int res1 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        //如果当前偷，那么左右不偷
        int res2 = curr.val + left[0] + right[0];

        return new int[]{res1, res2};
    }


    /**
     * 121. 买卖股票的最佳时机
     * 简单
     * 3.3K
     * 相关企业
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * <p>
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * <p>
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * <p>
     * 示例 1：
     * <p>
     * 输入：[7,1,5,3,6,4]
     * 输出：5
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     * 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     * 示例 2：
     * <p>
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
     * <p>
     * <p>
     * 提示：
     * <p>
     * 1 <= prices.length <= 105
     * 0 <= prices[i] <= 104
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        //贪心
        //int max = Integer.MIN_VALUE;
        //int low = Integer.MAX_VALUE;
        //for (int i = 0; i < prices.length; i++) {
        //   low = Math.min(low, prices[i]);
        //   max = Math.max(max, prices[i] - low);
        //}
        //return max;
        //
        //动态规划

        //定义dp数组，俩个状态,dp[i][0]表示：持有股票最大值，dp[i][1]表示不持有股票最大值
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);            //没买，或者是买了再买
        }

        return dp[prices.length - 1][1];        //这里dp[prices.length - 1][1]，是因为，最后肯定自己将股票卖了，或者干脆没有买入
    }


    /**
     * 122. 买卖股票的最佳时机 II
     * 中等
     * 2.4K
     * 相关企业
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     * 示例 1：
     * 输入：prices = [7,1,5,3,6,4]
     * 输出：7
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     * 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     * 总利润为 4 + 3 = 7 。
     * 示例 2：
     * 输入：prices = [1,2,3,4,5]
     * 输出：4
     * 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     * 总利润为 4 。
     * 示例 3：
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
     *
     * @param prices
     * @return
     */
    public int maxProfit1(int[] prices) {
        //定义dp数组，dp[i][0]的含义：持有股票,dp[i][1]的含义，不持有股票
        int[][] dp = new int[prices.length][2];
        //初始化
        dp[0][0] = -prices[0];

        //确认递推公式
        //确认循环顺序
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);        //持有股票，俩个可能，持有上个股票，这里不选择卖出，二，已经卖出，然后继续买入
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);                                               //不持有股票，俩个可能，干脆买买，或者是买了卖出
        }

        return dp[prices.length - 1][1];
    }


    /**
     * 123. 买卖股票的最佳时机 III
     * 困难
     * 1.6K
     * 相关企业
     * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
     * <p>
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入：prices = [3,3,5,0,0,3,1,4]
     * 输出：6
     * 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     * 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
     * 示例 2：
     * 输入：prices = [1,2,3,4,5]
     * 输出：4
     * 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     * 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     * 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     * 示例 3：
     * <p>
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
     * 示例 4：
     * <p>
     * 输入：prices = [1]
     * 输出：0
     * <p>
     * 提示：
     * <p>
     * 1 <= prices.length <= 105
     * 0 <= prices[i] <= 105
     * 通过次数
     * 302.7K
     * 提交次数
     * 50
     *
     * @param prices
     * @return
     */
    public int maxProfit3(int[] prices) {
        //定义dp数组,没有操作(即：原本兜子里的钱），第一次持有股票，第一次不持有股票，第二次持有股票，第二次不持有股票
        int[][] dp = new int[prices.length][5];
        //初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        //确认循环顺序
        for (int i = 1; i < prices.length; i++) {
            //第一次：买入股票，有俩个情况，当前买入，和买入后延续
            //
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            //卖出，买了又买，干脆没买
            dp[i][2] = Math.max(dp[i - 1][2], prices[i] + dp[i][1]);
            //买入股票，延续前面的，和干脆没买
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            //卖出，买了又买，没买
            dp[i][4] = Math.max(dp[i - 1][4], prices[i] + dp[i][3]);
        }
        return dp[prices.length - 1][4];
    }


    /**
     * 188. 买卖股票的最佳时机 IV
     * 困难
     * 1.1K
     * 相关企业
     * 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 示例 1：
     * 输入：k = 2, prices = [2,4,1]
     * 输出：2
     * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
     * 示例 2：
     * 输入：k = 2, prices = [3,2,6,5,0,3]
     * 输出：7
     * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     * 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
     * 提示
     * 1 <= k <= 100
     * 1 <= prices.length <= 1000
     * 0 <= prices[i] <= 1000
     *
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit4(int k, int[] prices) {
        //dp[i][0]表示不操作，即原本兜里的钱，dp[i][1]第一次买入，dp[i][2]第一次卖出，dp[i][3]第二次买入，dp[i][4]第二次卖出,...,...往复循环
        int[][] dp = new int[prices.length][2 * k + 1];
        //初始化
        dp[0][0] = 0;
        for (int i = 1; i < 2 * k + 1; i += 2) {      //1, 3
            dp[0][i] = -prices[0];
        }
        //确认循环顺序
        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j < 2 * k; j += 2) {
                //买入，或者保持现状 1,3,5,7,9,
                //dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                //不持有：卖出，或没买
                //dp[i][2] = Math.max(dp[i - 1][2], dp[i][1] + prices[i])
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
            }
        }
        return dp[prices.length - 1][2 * k];
    }


    /**
     * 309. 买卖股票的最佳时机含冷冻期
     * 中等
     * 1.7K
     * 相关企业
     * 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 示例 1:
     * 输入: prices = [1,2,3,0,2]
     * 输出: 3
     * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     * 示例 2:
     * 输入: prices = [1]
     * 输出: 0
     * 提示：
     * 1 <= prices.length <= 5000
     * 0 <= prices[i] <= 1000
     *
     * @param prices
     * @return
     */
    public int maxProfit5(int[] prices) {
        //定义dp数组，第i天的状态为j，剩余现金为dp[i][j]，四个状态：0买入，1保持卖出，2今天卖出，3冷冻
        int[][] dp = new int[prices.length][4];
        //初始化
        dp[0][0] = -prices[0];
        //确认循环顺序
        for (int i = 1; i < prices.length; i++) {
            //买入
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));

            //保持卖出
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
            //今天卖出
            dp[i][2] = dp[i - 1][0] + prices[i];
            //冷冻
            dp[i][3] = dp[i - 1][2];

        }
        return Math.max(dp[prices.length - 1][3], Math.max(dp[prices.length - 1][2], dp[prices.length - 1][1]));

    }


    /**
     * 714. 买卖股票的最佳时机含手续费
     * 提示
     * 中等
     * 1K
     * 相关企业
     * 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
     * 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
     * 返回获得利润的最大值。
     * 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
     * 示例 1：
     * 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
     * 输出：8
     * 解释：能够达到的最大利润:
     * 在此处买入 prices[0] = 1
     * 在此处卖出 prices[3] = 8
     * 在此处买入 prices[4] = 4
     * 在此处卖出 prices[5] = 9
     * 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
     * 示例 2：
     * 输入：prices = [1,3,7,5,10,3], fee = 3
     * 输出：6
     *
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit6(int[] prices, int fee) {
        //定义dp数组，持有股票，不持有股票
        int[][] dp = new int[prices.length][2];
        //初始化
        dp[0][0] = -prices[0];
        //确认循环顺序，确认递推公式
        for (int i = 1; i < prices.length; i++) {
            //持有股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
            //不持有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i][0] + prices[i] - fee);
        }
        return dp[prices.length - 1][1];

    }


    /**
     * 300. 最长递增子序列
     * 中等
     * 3.5K
     * 相关企业
     * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
     * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
     * 示例 1：
     * 输入：nums = [10,9,2,5,3,7,101,18]
     * 输出：4
     * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
     * 示例 2：
     * 输入：nums = [0,1,0,3,2,3]
     * 输出：4
     * 示例 3：
     * 输入：nums = [7,7,7,7,7,7,7]
     * 输出：1
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int res = 0;
        Arrays.fill(dp, 1);
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }


    /**
     * 674. 最长连续递增序列
     * 简单
     * 431
     * 相关企业
     * 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
     * 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,3,5,4,7]
     * 输出：3
     * 解释：最长连续递增序列是 [1,3,5], 长度为3。
     * 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
     * 示例 2：
     * 输入：nums = [2,2,2,2,2]
     * 输出：1
     * 解释：最长连续递增序列是 [2], 长度为1
     *
     * @param nums
     * @return
     */
    public int findLengthOfLCIS(int[] nums) {
        //自己的思路
        if (nums.length == 1) {
            return 1;
        }
        int res = 0;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                res++;
            } else {
                res = 0;
            }

            max = Math.max(res, max);
        }

        return max;

    }


    /**
     * 718. 最长重复子数组
     * 提示
     * 中等
     * 1K
     * 相关企业
     * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
     * 示例 1：
     * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
     * 输出：3
     * 解释：长度最长的公共子数组是 [3,2,1] 。
     * 示例 2：
     * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
     * 输出：5
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int findLength(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0) {
            return 0;
        }

        //定义dp数组
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        //初始化dp数组
        dp[0][0] = 0;
        //确认递归顺序
        //确认循环顺序
        int res = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }

        return res;

    }


    /**
     * 1143. 最长公共子序列
     * 提示
     * 中等
     * 1.5K
     * 相关企业
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
     * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
     * 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
     * <p>
     * <p>
     * 示例 1：
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
     * 示例 2：
     * 输入：text1 = "abc", text2 = "abc"
     * 输出：3
     * 解释：最长公共子序列是 "abc" ，它的长度为 3 。
     * 示例 3：
     * 输入：text1 = "abc", text2 = "def"
     * 输出：0
     * 解释：两个字符串没有公共子序列，返回 0 。
     * <p>
     * 提示：
     * 1 <= text1.length, text2.length <= 1000
     * text1 和 text2 仅由小写英文字符组成。
     *
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0) {
            return 0;
        }

        //定义dp数组，dp[i][j]表示text1[0, i - 1]和text2[0, j - 1]的最长公共子序列
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        //初始话dp
        dp[0][0] = 0;
        //确认递推公式
        //确认循环顺序
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[text1.length()][text2.length()];
    }


    /**
     * 1035. 不相交的线
     * 提示
     * 中等
     * 512
     * 相关企业
     * 在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
     * 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
     * nums1[i] == nums2[j]
     * 且绘制的直线不与任何其他连线（非水平线）相交。
     * 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
     * 以这种方法绘制线条，并返回可以绘制的最大连线数。
     * <p>
     * <p>
     * 示例 1：
     * 输入：nums1 = [1,4,2], nums2 = [1,2,4]
     * 输出：2
     * 解释：可以画出两条不交叉的线，如上图所示。
     * 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
     * 示例 2：
     * 输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
     * 输出：3
     * 示例 3：
     * 输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
     * 输出：2
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0) {
            return 0;
        }

        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }


    /**
     * 53. 最大子数组和
     * 中等
     * 6.5K
     * 相关企业
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组 是数组中的一个连续部分。
     * 示例 1：
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * 示例 2：
     * 输入：nums = [1]
     * 输出：1
     * 示例 3：
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     * 提示：
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     * <p>
     * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        //定义dp数组，以nums[i]为结尾的序列的最大和（意思就是，从前面某一个数开始，到nums[i]结尾的这个序列的最大和）
        int[] dp = new int[nums.length];
        //初始化
        dp[0] = nums[0];
        int res = nums[0];
        //确认递推公式    dp[i] = Math.max(dp[i - 1], dp[i - 1] + nums[i]);
        //确认循环顺序
        for (int i = 1; i < nums.length; i++) {

            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);

            res = Math.max(res, dp[i]);
        }
        return res;
    }


    /**
     * 392. 判断子序列
     * 简单
     * 972
     * 相关企业
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     * 进阶：
     * 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
     * 致谢：
     * 特别感谢 @pbrother 添加此问题并且创建所有测试用例。
     * 示例 1：
     * 输入：s = "abc", t = "ahbgdc"
     * 输出：true
     * 示例 2：
     * 输入：s = "axc", t = "ahbgdc"
     * 输出：false
     * <p>
     * <p>
     * 提示：
     * <p>
     * 0 <= s.length <= 100
     * 0 <= t.length <= 10^4
     * 两个字符串都只由小写字符组成。
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isSubsequence(String s, String t) {
        //if (s != null && s.length() == 0) {
        //    return true;
        //}
        //int indexS = 0;
        //int indexT = 0;
        //
        //for (; indexT < t.length(); indexT++) {
        //    if (s.charAt(indexT) == t.charAt(indexT)) {
        //        indexS++;
        //    }
        //
        //    if (indexS == s.length()) {
        //        return true;
        //    }
        //}
        //
        //return false;
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        dp[0][0] = 0;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        if (dp[s.length()][t.length()] == s.length()) {
            return true;
        }
        return false;
    }


    /**
     * 115. 不同的子序列
     * 困难
     * 1.2K
     * 相关企业
     * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
     * 示例 1：
     * 输入：s = "rabbbit", t = "rabbit"
     * 输出：3
     * 解释：
     * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
     * rabbbit
     * rabbbit
     * rabbbit
     * 示例 2：
     * 输入：s = "babgbag", t = "bag"
     * 输出：5
     * 解释：
     * 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
     * babgbag
     * babgbag
     * babgbag
     * babgbag
     * babgbag
     *
     * @param s
     * @param t
     * @return
     */
    public int numDistinct(String s, String t) {
        //判断s里面有几个t
        if (t.length() == 0) {
            return 1;
        }

        //定义dp数组
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        //初始化dp
        for (int i = 0; i <= s.length(); i++) {
            dp[i][0] = 1;
        }
        //确认递推公式
        //确认循环顺序
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[s.length()][t.length()];
    }


    /**
     * 583. 两个字符串的删除操作
     * 中等
     * 639
     * 相关企业
     * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
     * 每步 可以删除任意一个字符串中的一个字符。
     * 示例 1：
     * 输入: word1 = "sea", word2 = "eat"
     * 输出: 2
     * 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
     * 示例  2:
     * 输入：word1 = "leetcode", word2 = "etco"
     * 输出：4
     * 提示：
     * 1 <= word1.length, word2.length <= 500
     * word1 和 word2 只包含小写英文字母
     * 通过次数
     * 141.6K
     * 提交次数
     * 211.7K
     * 通过率
     * 66.9%
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }

        if (word2.length() == 0) {
            return word1.length();
        }
        //定义dp数组：表示word1[0: i - 1] 和 word2[0: j - 1]的字符串相同需要删掉dp[i][j]个字符
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //初始化，如果某个串为空，那么需要删除另一个字符串所有字符
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }

        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }

        //确认递归顺序
        //确认递推公式
        //俩种情况：
        //1：word1[i - 1] == word2[j - 1]        不需要删除字符，步数不变
        //2：word1[i - 1] != word2[j - 1]        步数加一：这里看需要删哪个
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];        //不删除字符，步数不变
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }


    /**
     * 72. 编辑距离
     * 中等
     * 3.2K
     * 相关企业
     * 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
     * 你可以对一个单词进行如下三种操作：
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     * 示例 1：
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     * 示例 2：
     * 输入：word1 = "intention", word2 = "execution"
     * 输出：5
     * 解释：
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance2(String word1, String word2) {
        if (word1.length() == 0) {
            return word2.length();
        }

        if (word2.length() == 0) {
            return word1.length();
        }

        //定义dp数组，word1[0: i - 1]到word2[0: j - 1]的最短编辑距离是dp[i][j]
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //初始化
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }

        //确认循环顺序
        //确认递推公式
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                } else {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }

        return dp[word1.length()][word2.length()];
    }


    /**
     * 647. 回文子串
     * 提示
     * 中等
     * 1.3K
     * 相关企业
     * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
     * 回文字符串 是正着读和倒过来读一样的字符串。
     * 子字符串 是字符串中的由连续字符组成的一个序列。
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     * 示例 1：
     * 输入：s = "abc"
     * 输出：3
     * 解释：三个回文子串: "a", "b", "c"
     * 示例 2：
     * 输入：s = "aaa"
     * 输出：6
     * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
     *
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        //定义dp数组，s[i: j]的字串是否为回文子串
        //boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化

        //确认递推公式
        //确认循环顺序
        //int res = 0;
        //for (int i = s.length() - 1; i >= 0; i--) {
        //    for (int j = i; j < s.length(); j++) {
        //        if (s.charAt(i) == s.charAt(j)) {
        //            if (j - i <= 1) {       //a /  aa
        //                dp[i][j] = true;
        //                res++;
        //            } else {
        //                dp[i][j] = dp[i + 1][j - 1];
        //                if (dp[i][j]) {
        //                    res++;
        //                }
        //            }
        //        }
        //    }
        //}
        //
        //return res;
        //01 02 03   12 13   23      a ab abc b bc c
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (isSubStr(s.substring(i, j))) {
                    res++;
                }
            }
        }
        return res;
    }


    /**
     * 516. 最长回文子序列
     * 中等
     * 1.1K
     * 相关企业
     * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
     * <p>
     * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "bbbab"
     * 输出：4
     * 解释：一个可能的最长回文子序列为 "bbbb" 。
     * 示例 2：
     * <p>
     * 输入：s = "cbbd"
     * 输出：2
     * 解释：一个可能的最长回文子序列为 "bb" 。
     *
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {
        //定义dp数组，s[i:j]范围内最长回文子序列为dp[i][j]
        int[][] dp = new int[s.length()][s.length()];
        //初始化dp

        //确认循环顺序
        //确认递推公式
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j == j) {
                        dp[i][j] = dp[i + 1][j - 1] + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 1;
                    }
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[0][s.length() - 1];
    }

    public boolean isSubStr(String s) {
        int first = 0;
        int last = s.length() - 1;

        while (first <= last) {
            if (s.charAt(first) != s.charAt(last)) {
                return false;
            }

            first++;
            last--;
        }

        return true;
    }




    public static void main(String[] args) {
        Solution so = new Solution();



    }


}
